package memory;


import java.util.Arrays;

public class Exercises1 {
    // 509、斐波那契
    int[] memo = new int[31]; // 备忘录

    public int fib(int n) {
        // 记忆化搜索

        //初始化
        Arrays.fill(memo,-1);

        return dfs(n);
    }

    public int dfs(int n) {
        // 进入递归就判断备忘录中是否存在
        if (memo[n] != -1) {
            // 存在直接返回
            return memo[n];
        }

        // 不存在就开始判断并且进行递归
        if(n == 0 || n == 1) {
            memo[n] = n;
            return n;
        }

        memo[n] = dfs(n - 1) + dfs(n - 2);
        return memo[n];
    }
}
